Choice constructs are an important part of the language of logic programming, yet the study of their semantics has been a challenging task. So far, only two-valued semantics have been studied, and the different proposals for such semantics have not been compared in a principled way. In this paper, an operator-based framework allow for the definition and comparison of different semantics in a principled way is proposed.

Semantics of various formalisms for knowledge representation can often be described by fixpoints of corresponding operators. For example, in many logics theories of a set of formulas can be seen as fixpoints of the underlying consequence operator [52]. Likewise, in logic programming, default logic or formal argumentation, all the major semantics can be formulated as different types of fixpoints of the same operator (see [22]). Such operators are usually non-monotonic, and so one cannot always be sure whether their fixpoints exist, and how they can be constructed. In order to deal with this'illusive nature' of the fixpoints, Denecker, Marek and Truszczyński [22] introduced a method for approximating each value z of the underlying operator by a pair of elements (x, y). These elements intuitively represent lower and upper bounds on z, and so a corresponding approximation operator for the original, non-monotonic operator, is constructed. If the approximating operator that is obtained is precision-monotonic, intuitively meaning that more precise inputs of the operator give rise to more precise outputs, then by Tarski and Knaster's Fixpoint Theorem the approximating operator has fixpoints that can be constructively computed, and which in turn approximate the fixpoints of the approximated operator, if such fixpoints exist. The usefulness of the algebraic theory that underlies the computation process described above was demonstrated on several knowledge representation formalisms, such as propositional logic programming [20], default logic [23], autoepistemic logic [23], abstract argumentation and abstract dialectical frameworks [50], hybrid MKNF [39], the graph description language SCHACL [11], and active integrity constraints [10], each one of which was shown to be an instantiation of this abstract theory of approximation.

SHACL is a W3C-proposed language for expressing structural constraints on RDF graphs. The recommendation only specifies semantics for non-recursive SHACL; recently, some efforts have been made to allow recursive SHACL schemas. In this paper, we argue that for defining and studying semantics of recursive SHACL, lessons can be learned from years of research in non-monotonic reasoning. We show that from a SHACL schema, a three-valued semantic operator can directly be obtained. Building on Approximation Fixpoint Theory (AFT), this operator immediately induces a wide variety of semantics, including a supported, stable, and well-founded semantics, related in the expected ways. By building on AFT, a rich body of theoretical results becomes directly available for SHACL. As such, the main contribution of this short paper is providing theoretical foundations for the study of recursive SHACL, which can later enable an informed decision for an extension of the W3C recommendation.

Abstract dialectical frameworks (ADFs) have recently been proposed as a versatile generalization of Dung's abstract argumentation frameworks (AFs). In this paper, we present a comprehensive analysis of the computational complexity of ADFs. Our results show that while ADFs are one level up in the polynomial hierarchy compared to AFs, there is a useful subclass of ADFs which is as complex as AFs while arguably offering more modeling capacities. As a technical vehicle, we employ the approximation fixpoint theory of Denecker, Marek and Truszczyński, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.